package com.leetcode.根据算法进行分类.排序算法相关.桶排序;

/**
 * @author: xiaomi
 * @date: 2021/3/13
 * @description: 164. 最大间距
 * https://leetcode-cn.com/problems/maximum-gap/
 * 【最大间距问题：优先考虑-桶排序】
 */
public class C_164_最大间距 {

    static C_164_最大间距 action = new C_164_最大间距();

    public static void main(String[] args) {
//        test1();
        test2();
    }


    public static void test1() {
        // 3
        int[] nums = new int[]{3, 6, 9, 1};
        int res = action.maximumGap(nums);
        System.out.println("res = " + res);
        //[]
    }

    public static void test2() {
        // 3
        int[] nums = new int[]{100, 3, 2, 1};
        int res = action.maximumGap(nums);
        System.out.println("res = " + res);
    }


    /**
     * 没想到这是一道困难题。
     * 不过如果没有特殊的限制，我也想不出来！
     * --
     * 桶排序
     * 1.找出max min
     * 2.关于桶数量的确认：我是这么认为的：
     * 从 min ~ max 的区域中，平均分割 len-2 次，于是产生了 len-1 个区域，这就是 桶的数量；
     * 3.设计每个桶（bucketMax,bucketMin）
     * res = Math.max(b[i]min-b[i-1]max)
     *
     * @param nums
     * @return
     */
    public int maximumGap(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return 0;
        }
        if (len == 2) {
            return Math.abs(nums[0] - nums[1]);
        }
        //1.找出 max min
        int max = nums[0], min = max;
        for (int i = 1; i < len; i++) {
            max = Math.max(nums[i], max);
            min = Math.min(nums[i], min);
        }
        //2.补充
        int size = len - 1;
        //此时可以保证  res>=distance
        if (max == min) {
            return 0;
        }
        int distance = (max - min) / size + 1;
        //distance = (max - min) % size == 0 ? distance : distance + 1;
        Integer[][] buckets = new Integer[size][2];
        int index = 0;
        for (int i = 0; i < len; i++) {
            index = (nums[i] - min) / distance;
            if (buckets[index][0] == null && buckets[index][1] == null) {
                //如果桶还木有放置元素
                buckets[index][0] = nums[i];
                buckets[index][1] = nums[i];
            } else if (nums[i] < buckets[index][0]) {
                //如果当前值小于 桶的 min -> 更新
                buckets[index][0] = nums[i];
            } else if (nums[i] > buckets[index][1]) {
                buckets[index][1] = nums[i];
            }
        }

        //3.遍历桶
        int res = distance;
        //由于 min 肯定非空
        int lastMax = buckets[0][1];
        for (int i = 0; i < size; i++) {
            if (buckets[i][0] == null) {
                continue;
            }
            //如果此时 buckets[i] 不为空
            res = Math.max(res, buckets[i][0] - lastMax);
            lastMax = buckets[i][1];
        }
        return res;
    }
}
